GBDT 算法原理

泰勒公式介绍

公式 \[f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(x_{0})}{n!}(x-x_{0})^{n}\]
- 一阶泰勒展开： \[f(x)\approx f(x_{0})+{f}'(x_{0})(x-x_{0})\]
- 二阶泰勒展开： \[f(x)\approx f(x_{0})+{f}'(x_{0})(x-x_{0})+{f}''(x_{0})\frac{(x-x_{0})^2}{2}\]
- 迭代形式：假设 $x^{t}=x^{t-1}+\Delta x$ 将 $f(t^{t})在x^{t-1}$ 处进行泰勒展开 \[\begin{align*} f(x^{t})&=f(x^{t-1}+\Delta x) \\ &\approx f(x^{t-1})+{f}'(x^{t-1})\Delta x+{f}''(x^{t-1})\frac{\Delta x^{2}}{2} \end{align*}\]

梯度下降法介绍

在机器学习任务中，需要最小化随时函数 $L(\theta)$,其中 $\theta$ 是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法:选取初值$\theta^0$，不断迭代，更新$\theta$的值，进行损失函数的极小化。 - 迭代公式： $\theta^{t}=\theta^{t-1}+\Delta\theta$ - 将 $L(\theta^{t})$ 在$\theta^{t-1}$处进行一阶泰勒展开： \[\begin{align*} L(\theta^t)&=L(\theta^{t-1}+\Delta\theta)\\ &\approx L(\theta^{t-1})+{L}'(\theta^{t-1})\Delta\theta \end{align*}\]

要使得$L(\theta^{t})$<$L(\theta^{t-1})$,可取：$\Delta\theta=-\alpha{L}’(\theta^{t-1})$，则：$\theta^t=\theta^{t-1}-\alpha{L}'(\theta^{t-1})$ 这里$\alpha$是步长，可以通过line search 确定，但是一般直接赋一直小的数。 ## 牛顿法
将$L(\theta^t)$ 在$\theta^{t-1}$处进行二阶泰勒展开： \[L(\theta^t)\approx L(\theta^{t-1})+{L}'(\theta^{t-1})\Delta\theta+{L''}(\theta^{t-1})\frac{\Delta\theta^2}{2}\] 为了简化分析过程，假设参数是标量（即$\theta$只有一维），则可将一阶和二阶导数分别记为$g$和$h$： \[L(\theta^t)\approx L(\theta^{t-1})+g\Delta\theta+h\frac{\Delta\theta^2}{2}\]
要使得$L(\theta^t)$极小，即让$g$和$h$: \[L(\theta^t)\approx L(\theta^{t-1})+g\Delta\theta+h\frac{\Delta\theta^2}{2}\]
要使得$L(\theta)$极小，即让 $g\Delta\theta+h\frac{\theta^{2}}{2}$ 极小，可令: \[\frac{\partial(g\Delta\theta+h\frac{\Delta\theta^2}{2}) }{\partial \Delta\theta}=0\] 求得 $\Delta\theta = -\frac{g}{h}$，故 $\theta^{t}=\theta^{t-1}+\Delta\theta=\theta^{t-1}-\frac{g}{h}$ 参数$\theta 推广到向量形式，迭代公式：\theta^t=\theta^{t-1}-H^{-1}g$ 这里$H$ 是海森矩阵

从参数空间到函数空间

GBDT 在函数空间中利用梯度下降法进行优化
XGBoost 在函数空间中利用牛顿法进优化

从Gradient Decend 到Gradient Boosting

参数空间

\[\theta^t(第t次迭代后的参数)=\theta^{t-1}(第t-1次迭代后的参数)+\theta_t(第t次迭代的参数增量)\]

参数更新方向后负梯度方向 \[\theta_t=-a_{t}g_{t}\]
最终参数等于每次迭代的增量的累加和 \[\theta = \sum_{t=0}^{T}\theta^t\]
$\theta_0为初值$

函数空间

\[f^t(x) (第t次迭代后的函数)=f^{t-1}(x)(第t-1次迭代后的函数)+f_t(x)(第t次迭代的函数增量)\] - 同样地，拟合负梯度 \[f_t(x)=-a_tg_t(x)\] - 最终函数等于每次迭代的增量的累加和 \[F(x)=\sum_{t=0}^{T}f_t(x)\] - $f_0(x)为模型初始值，通常为常数$

从Newton’s Method 到 Newton Boosting

参数空间

\[\theta^t(第t次迭代后的参数)=\theta^{t-1}(第t-1次迭代后的参数)+\theta_t(第t次迭代的参数增量)\]

与梯度下降法唯一不同的就是参数增量 \[\theta_t=-H_{t}^{-1}g_{t}\]
最终参数等于每次迭代的增量的累加和 \[\theta = \sum_{t=0}^{T}\theta^t\]
$\theta_0为初值$

函数空间

\[f^t(x) (第t次迭代后的函数)=f^{t-1}(x)(第t-1次迭代后的函数)+f_t(x)(第t次迭代的函数增量)\] - 同样地，拟合负梯度 \[f_t(x)=- \frac {g_t(x)}{h_t(x)}\] - 最终函数等于每次迭代的增量的累加和 \[F(x)=\sum_{t=0}^{T}f_t(x)\] - $f_0(x)为模型初始值，通常为常数$

小结

Boosting 算法是一种加法模型（additive training） \[F(x)=\sum_{t=0}^{T}f_t(x)\]

Gradient Boosting Tree 算法原理

其模型F 定义为加法模型： \[F(X;w)=\sum_{t=0}^{T}\alpha_th_t(x;w_t)=\sum_{t=0}^{T}f_t(x;w_t)\] 其中，x为输入样本，h为分类回归树，w是分类回归树的参数，$\alpha$是每课树的权重。
通过最小化损失函数求解最优模型： \[F^*=\arg \min_{F}\sum_{i=0}^{N}L(y_i,F(x_i;w))\] NP 难问题 —> 通过贪心算法，迭代求解局部最优化

输入：$(x_i,y_i),T,L$ 1. 初始化 $f_0$

for t=1 to T do 2.1. 计算相应: \[y_i=-\left [ \frac{\partial L(y_i,F(x_i)) }{\partial F(x_i) } \right ]_{F(x)=F_{t-1}(x)},i=1,2,...N\] 2.2. 学习第t棵树: \[w^* = \arg\min_{t}\sum_{i=1}^{N}(y_i-h_t(x_i;w))^2\] 2.3. line search 找步长:\[\rho^* = \arg\min_{\rho}\sum_{i=1}^{N}L(y_i,F_{t-1}(x_i)+\rho h_{t}(x_i;w^*))\] 2.4. 令\[f_t=\rho^*h_t(x;w^*)\]更新模型：$F_t= F_{t-1}+f_t$
输出$F_T$

GBDT 例子

本文将从一个简单的示例开始。我们希望根据一个人是否玩视频游戏、是否喜欢园艺以及戴帽子时的特点来判断这个人的年龄。我们总共有九个训练样本来构建模型。 enter image description here

梯度下降接下来，让我们使用梯度下降的概念把这个想法形式化。假设我们有一个希望最小化的可微函数。例如 \[L(x_1,x_2)=\frac{1}{2}(x_1-15)^2+\frac{1}{2}(x_2-25)^2\] 我们的目标是找到一组能够最小化L的(x1, x2)。注意，这个函数可以理解为给定两个预测值x1和x2，计算其与两个数据点15和25的均方误差（使用1/2乘子更有利于梯度的计算）。尽管我们可以直接最小化这个函数，但是在面对更复杂的损失函数时，我们往往无法直接最小化损失函数，而梯度下降则为我们提供了一种可行的方式。

初始阶段： - 迭代次数M=100 - 迭代起始点s0=(0,0) - 迭代步长γ=0.1 在第m次迭代过程中（m取值从1到M）： - 计算函数L在数据点$s^{(m-1)}$处的梯度 - 沿梯度最大方向（梯度的反方向）前进步长γ的距离。公式如下： \[s^m=s^{(m-1)}-\gamma\Delta L(s^{(m-1)})\] 如果$\gamma$很小且$M$足够大，那么$s^{M}$将落在函数$L$的最小值处

应用梯度下降现在，我们可以在前面的梯度提升模型中使用梯度下降了。我们需要最小化的目标函数是L。我们的起始点是F0(x)。在模型第一次迭代m=1时，我们计算L关于F0(x)的梯度。然后，我们将一个弱分类器调整为梯度分量。在回归树的例子中，叶子节点会在具有相似特征的样本间计算梯度均值。对于每一个叶子节点，我们沿梯度均值的方向更新参数（使用线性搜索来确定步长的大小）。更新后的结果记为F1。随后，我们反复重复这个过程，直到得到FM。

我们修改了前面提到的梯度提升算法，使其适用于任何可微损失函数。现在，让我们忘记前面的想法，从另外一个角度重新考虑我们的梯度提升模型。

使用常量来初始化模型： \[F_0(X)=\arg\min_{\gamma}\sum_{i=1}^{n}L(y_i,\gamma)\]
m从1到M：
- 计算伪残差
- 根据伪残差拟合基本学习器$h_m(x)$
- 计算步长乘子$\gamma_m$（在树形模型的情况下，需要为每一个叶子节点计算不同的$\gamma_m$）
- 更新$F_m(x)=F_{m-1}(x)+\gamma_mh_m(x)$ 如果你想要检测自己对梯度提升的理解是否正确，我们目前的梯度提升方法应用于示例问题的均方误差和绝对误差结果如下：

Newton Boosting Tree 算法原理：详解XGBoost

模型函数形式

给定数据集$D = \{(x_i,y_i)\}$，XGBoost进行additive training，学习K棵树，采用以下函数对样本进行预测： \[\hat{y_i}= \phi(x_i)=\sum_{k=1}^{K}f_k(x_i), f_k\in F\] 这里$F$是假设空间，$f(x)$是回归树(CART): \[F=\{f(x)=w_{q(x)}\}(q:\mathbb{R}^{m}\rightarrow T,w\in \mathbb{R}^T)\] $q(x)$表示将样本x分到了某个叶子节点上，$w$是叶子节点的分数（leaf score）,所以$w_q(x)$表示回归树对样本的预测值

例子：预测一个人是否喜欢电脑游戏回归树的预测输出是实数分数，可以用于回归，分类，排序等任务中。对于回归问题，可以直接作为目标值，对于分类问题，需要映射成概率，比如采用逻辑函数$\sigma(z)=\frac{1}{1+e^{-z}}$

目标函数

参数空间中的目标函数： \[Obj(\Theta) = L(\Theta)(误差函数)+\Omega(\Theta)(正则化项)\] 误差函数可以是square loss,logloss等，正则项可以是L1正则，L2正则等。 Ridge Regression(岭回归):\[\sum_{i=1}^{n}(y_i-\theta^Tx_i)^2+\lambda\left \|\theta \right \|^2\] LASSO :\[\sum_{i=1}^{n}(y_i-\theta^Tx_i)^2+\lambda\left \|\theta \right \|_1\]

正则项

正则项的的作用，可以从几个角度去解释：
- 通过偏方差分解去解释
- PAC-learning 泛化界解释
- Bayes 先验解释，把正则当成先验
从Bayes 角度来看，正则相当于对模型参数引入先验分布： L2正则，模型参数服从高数分布$\theta\sim N(0,\sigma ^2)$对参数加了分布约束，大部分绝对值很小 L1 正则，模型参数服从拉普拉斯分布对参数界了分布约束，大部分取值为0
XGBoost 的目标函数(函数空间) \[L(\phi) = \sum_{i}l(\hat(y_i),y_i)+\sum_{k}\Omega(f_k)\] 正则项对每棵回归树的复杂度进行了惩罚
相比原始的GBDT,XGBoost 的目标函数多了正则项，使得学习出来的模型更加不容易过拟合
又哪些指标可以衡量树的复杂度？树的深度，内部节点的个数，叶子节点的个数（T）,叶节点分数（w）。。。 XGBoost 采用的： \[\Omega(f)=\gamma T+\frac{1}{2}\lambda \left \| \omega \right \|^2\] 对叶子节点个数进行惩罚，相当于再训练过程中做了剪枝

误差函数的二阶泰勒展开

第t次迭代后，模型的预测等于前t-1次的模型预测加上第t棵树的预测： \[\hat{y_i}^{(t)}=\hat{y_i}^{(t-1)}+f_t(x_i)\]
此时目标函数可写作： \[L^{(t)}=\sum_{i=1}^{n}l(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)\] 公式中 $y_i$,$\tilde{y_i}^{(t-1)}$都已知，模型要学习的只有第t棵树$f_t$
将误差函数再$\tilde{y_i}^{(t-1)}$处进行二次泰勒展开： \[L^{(t)}\simeq \sum_{i=1}^{n}[l(y_i,\hat{y}^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\] 公式中: $g_i=\partial_{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)})$
$h_i=\partial_{\hat{y}^{(t-1)}}^{2}l(y_i,\hat{y}^{(t-1)})$
将公式中的常数项去掉，得到: \[\tilde{L}^{(t)}=\sum_{i=1}^{n}[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\]
把$f_t,\Omega(f_t)$写成树结构的形式，即把下式代入目标函数中 $f(x)=\omega _{q(x)}$ $\Omega(f)=\gamma T+\frac{1}{2}\lambda\left \|\omega \right \|^2$
得到： \[\begin{align*} L^{(t)}&=\sum_{i=1}^{n}[g_if_i(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\\ &=\sum_{i=1}^{n}[g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_q(x_i)](对样本累加)+\gamma T+\lambda \frac{1}{2}\sum_{j=1}^{T}w_j^2(对叶节点累加) \end{align*}\]
怎么统一起来？定义每个叶节点j上的样本集合为 $I_j = {i q(x_i)=j } $ 则目标函数可以写成按叶节点累加的形式: \[\begin{align*} L^{(t)}&=\sum_{j=1}^{T}\bigg[(\sum_{i\in I_j}g_i)w_{i}+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w^2_j\bigg]+\gamma T\\ &=\sum_{j=1}^{T}\bigg[(G_jw_{i}+\frac{1}{2}(H_j+\lambda)w^2_j\bigg]+\gamma T \end{align*}\]
如果确定了树的结构（即q(x)确定），为了使目标函数最小，可以令其导数为0，解得每个叶节点得最优预测分数为： \[w^*_j=-\frac{G_j}{H_j+\lambda}\] 代入目标函数，得到最小损失为： \[L^*=-\frac{1}{2}\sum_{j=1}^{T}\frac{G^2_j}{H_j+\lambda}+\gamma T\]

回归树得学习策略

当回归树得结构确定时，我们前面已经推导出其最优得叶节点分数以及对应得最小损失值，问题是怎么确定树的结构？
- 暴力枚举所以可能的树结构，选择损失值最小的 -NP难问题。
- 贪心法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的。
分裂前后的增益怎么计算
- ID3算法采用信息增益
- C4.5算法采用信息增益比
- CART 采用Gini 系数 XGBoost 呢？

XGBoost 的打分函数

\[L^*=-\frac{1}{2}\sum_{j=1}^{T}\color{Red}{\frac{G_j^2}{H_j+\lambda}}+\gamma T\] 标红部分衡量了每个叶子节点对总体损失的贡献，我们希望损失越小越好，则标红部分的值越大越好。因此，对一个叶子节点进行分裂，分裂前后的增益定义为：

\[Gain = \frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_R+G_L)^2}{H_R+H_L+\lambda}-\gamma\]

Gain 的值越大，分裂后L减少越多。所以当对一个叶节点分割时，计算所又候选对应的gain,选取gain最大的进行分割

树节点分裂方法（Split Finding）

暴力枚举遍历所有特征的所有可能的分割点，计算gain值，选取值最大的（feature，value）去分割
近似方法对于每个特征，只考察分位点，减少计算复杂度举例：三分位数
实际上XGBoost 不是简单地按照样本个数进行分位，而是以二阶导数值作为权重，比如：
为什么用$h_i$加权？把目标函数整理成以下形式，可以看出$h_i$又对loss加权作用 \[\sum_{i=1}^{n}\frac{1}{2}h_i(f_t(x_i)-\frac{g_i}{h_i})^2+\Omega(f_t)+constant\]